# 1.2 List all the different ways to connect two different objects for the example in Figure 1.1.
# 使用图将问题转换为不同顶点之间是否存在路，如果存在，请输出该路径

def main():
    # 构建邻接表
    edges = {
        (3,4), (4,9), (8,0), (2,3), (5,6), (2,9), (5,9), (7,3),
        (4,8), (0,2), (6,1)
    }
    adj = {i: [] for i in range(10)}
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    # 查找所有连通分量
    visited = set()
    components = []
    for node in range(10):
        if node not in visited:
            stack = [node]
            visited.add(node)
            component = []
            while stack:
                current = stack.pop()
                component.append(current)
                for neighbor in adj[current]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)
            components.append(sorted(component))
    
    # 找出所有连通分量内的顶点对并生成路径
    def find_all_paths(start, end):
        paths = []
        visited_nodes = set()
        
        def dfs(current, path):
            if current == end:
                paths.append(path.copy())
                return
            visited_nodes.add(current)
            for neighbor in adj[current]:
                if neighbor not in visited_nodes:
                    path.append(neighbor)
                    dfs(neighbor, path)
                    path.pop()
            visited_nodes.remove(current)
        
        dfs(start, [start])
        return paths
    
    # 输出结果
    for component in components:
        n = len(component)
        for i in range(n):
            u = component[i]
            for j in range(i + 1, n):
                v = component[j]
                paths = find_all_paths(u, v)
                for path in paths:
                    print(' '.join(map(str, path)))
                    
if __name__ == "__main__":
    main()